package mao.leetcode.others.leetcode94;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {
    List<Integer> list = new ArrayList<>();
    int maxDepth;
    int count;
    public static void main(String[] args) {

    }
    //leecode 94题
    //增加一个标签，表示已经展开过了还是没有展开过
    public List<Integer> inorderTraversal_3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null ) return list;
        Stack<ColoredTreeNode> s = new Stack<>();
        s.push(new ColoredTreeNode(true,root));
        while ( !s.isEmpty()){
            ColoredTreeNode n = s.pop();
            if (n.node == null) continue;
            if (n.folded){
                s.push(new ColoredTreeNode(true,n.node.right));
                n.folded=false;
                s.push(n);
                s.push(new ColoredTreeNode(true,n.node.left));
            }else list.add(n.node.val);
        }
        return list;
    }
    public class ColoredTreeNode{
        boolean folded = true;
        TreeNode node;
        public ColoredTreeNode(boolean folded, TreeNode node) {
            this.folded = folded;
            this.node = node;
        }
    }

    //莫里斯遍历，使用到了线索二叉树结构
    public List<Integer> inorderTraversal_2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null){
            if (cur.left == null){
                list.add(cur.val);
                cur=cur.right;  //只可能由于此处导致  cur = null;
            }else {
                TreeNode pre = cur.left;
                while (pre.right != null) pre=pre.right; //找到前驱节点
                pre.right = cur;
                TreeNode temp = cur;
                cur = cur.left;
                temp.left = null;
            }
        }
        return list;
    }

    //中序遍历的迭代写法，尝试改成前和后。
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); //需要处理的
        TreeNode cur = root;  //正在处理的
        while (cur != null || !stack.isEmpty()){
            while (cur != null){  //递归左侧，由于一直查找到 cur == null 所以右侧节点也可以被处理。
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur == null)  continue;
            list.add(cur.val); //递归中间
            cur= cur.right;    //处理右侧
        }
        return list;
    }
//    public List<Integer> inorderTraversal(TreeNode root) {
//        if (root == null) return list;
//        inorderTraversal(root.left);
//        list.add(root.val);
//        inorderTraversal(root.left);
//        return list;
//    }
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

}
